#!/usr/bin/env python
from collections import deque

def topological_sort_dfs(vertex, graph):
    def dfs(i, adjacency, flags, ans):
        if flags[i] == -1: 
            return True
        if flags[i] == 1: return False
        flags[i] = 1
        for j in adjacency[i]:
            if not dfs(j, adjacency, flags, ans): return False
        flags[i] = -1
        ans.append(i)
        return True

    adjacency = [[] for _ in range(vertex)]
    flags = [0 for _ in range(vertex)]
    for info in graph:
        adjacency[info[1]].append(info[0])
    
    for i in range(vertex):
        if not dfs(i, adjacency, flags): return False
    return True

def topological_sort_bfs(vertex, graph):
    indegress = [0 for _ in range(vertex)]
    adjacency = [[] for _ in range(vertex)]
    queue = deque()
    ans = []

    for info in graph:
        indegress[info[0]] += 1
        adjacency[info[1]].append(info[0])
    
    for i in range(len(indegress)):
        if indegress[i] == 0: 
            queue.append(i)
    
    while len(queue) != 0:
        pre = queue.popleft()
        ans.append(pre)
        for cur in adjacency[pre]:
            indegress[cur] -= 1
            if indegress[cur] == 0:
                queue.append(cur)
    
    return ans

    